// 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

const longestSubstring = function (s: string, k: number): number {
    // 递归出口，当子字符串的长度小于k值是不成立
    if (s.length < k) {
        return 0;
    }
    // 统计哈希表
    const hashMap = new Map<string, number>();
    for (let i = 0; i < s.length; i++) {
        const count: number = hashMap.get(s[i]) ?? 0;
        hashMap.set(s[i], count + 1);
    }
    // 遍历哈希表
    for (let [str, count] of hashMap.entries()) {
        // 如果出现了字符t它的计数不满足k的要求
        if (count < k) {
            const strFragments: string[] = s.split(str); // 对字符t进行分片
            const subRes: number[] = []; // 用于存储分片的结果
            for (let subStr of strFragments) {
                subRes.push(longestSubstring(subStr, k));
            }
            return Math.max(...subRes); // 对分片结果求最大
        }
    }
    return s.length; // 最理想的情况，所有字符满足k，直接返回字符长度即可
};


// 这道题目初步一看会认为是一道滑动窗口相关的题目
// 但实际上这道题基于滑动窗口方法解决会非常的困难（在于如何维护或撤销字符计数上）
// 不太好想到这道题目可以使用递归分治的方法来求解
// 首先我们定义递归函数的作用：
// 这个函数负责找到求一个最长的子字符串的长度（该子字符串中每个字符出现的次数都最少为 k）
// 实质上就是题目的要求
// 我们先思考边界情况，边界情况非常简单，当字符串长度小于 k 时，肯定不满足题目条件
// 此时子串长度直接返回 0
// 然后我们再思考正常情况：我们是需要知道当前子串各个字符的计数的，这里就可以采用哈希表来解决
// 哈希表拿到字符计数之后，最理想的情况肯定是每个字符都大于等于k，此时我们直接返回字符长度就可以了（肯定是最大的）
// 但接下来我们可能也会遇到这个情况：其中有一个字符 x 它的计数不满足k，
// 重点来了，那么当前字符的所有包含 x 的子串必然也不满足题目要求，我们以t作为基准分片
// 分片后得到的子串再各个分别递归调用原函数（我们就把大问题拆成了重复的小问题）
// 之后我们再逐一统计长度即可。